This code shows that small Baker-Luecke knots do not have Alexander polynomials in D.

In [2]:
##This is code that will search for an obtuse superbase
##in an integer CM lattice. Input is a list of
##coefficients for CM lattice.

#from itertools import combinations
#import numpy as np
import sympy as sp
import time
import math

def is_tight(sigma):
    #Check whether a CM lattice has a tight index.
    for i in range(1,len(sigma)):
        if sigma[i]==1+ sum([sigma[j] for j in range(0,i)]):
            return True
    return False

def is_CM(sigma):
    ##Check the vector satisfies the CM condition
    for i in range(1,len(sigma)):
        if sigma[i]> 1+sum([sigma[j] for j in range(0,i)]):
            return False
    return True

def stable_is_decomposable(stable_coefs):
    #Check whether any changemaker lattice associated to a set of stable
    #coefficients can possibly be decomposable
    stable=sorted(stable_coefs)
    
    return is_decomposable([1]*stable[0]+stable)

def is_decomposable(sigma):
    #Check whether a given changemaker lattice
    #is decomposable.
    ##Uses Greene's algorithm of calculating the standard
    ##basis elements and checking that their intersection
    ##graph is connected.
    if is_tight(sigma) or not is_CM(sigma):
        return False

    STD_basis=[]
    n=len(sigma)
    for i in range(1,n):
        v=[0]*n
        v[i]=-1
        T=sigma[i]
        j=i
        while T>0:
            j=max([k for k in range(0,j) if sigma[k]<=T])
            v[j]=1
            T-=sigma[j]
        STD_basis.append(list(v))
    
    S1=[STD_basis[0]]
    S2=[]
    for i in range(1,len(STD_basis)):
        v=STD_basis[i]
        flag=True
        for w in S1:
            if sum([v[j]*w[j] for j in range(0,n)])!=0:
                flag=False
                S1.append(list(v))
                break
        if flag:
            S2.append(list(v))
            
    if len(S2)==0:
        return False
    for v in S2:
        for w in S1:
            if sum([v[j]*w[j] for j in range(0,n)])!=0:
                return False
    return True

def norm(v):
    return sum([z*z for z in v])

def irred_check(v,vtest):
    #Computes T=(v-vtest).vtest returns true if this does not prove
    #that v is reducible. I.e returns true if T<0 or vtest=0 or v=vtest.

    T=sum([(v[i]-vtest[i])*vtest[i] for i in range(0,len(v))])
    if T<0:
        return True

    if T==0:
        if sum([z*z for z in vtest])==0:
            return True
        if sum([(v[i]-vtest[i])*(v[i]-vtest[i]) for i in range(0,len(v))])==0:
            return True
    return False
    
def vertex_bounds(sigma):
    #Provide bounds on the coefficients of a vertex in
    #in an OSB in a changemaker lattice.
    n=len(sigma)
    vmax=[0]*n
    p=norm(sigma)
    #Check if sigma is tight
    vmax[0]=1
    if is_tight(sigma):
        vmax[0]=2
    else:
        vmax[0]=1
    
    for i in range(1, len(sigma)):
        if sigma[i]==sigma[i-1]:
            vmax[i]=vmax[i-1]
            continue

        if sigma[i-1]==1 and sigma[i]>1:
            vmax[i]=sigma[i]
            continue   
        
        #If sigma[i] tight.
        if sigma[i]> sum([sigma[j] for j in range(0,i)]):
            vmax[i]=5+sum([vmax[j]+1 for j in range(0,i)])
        else:
            T=sigma[i]
            j=i-1
            while T>0:
                j=max([k for k in range(0,j+1) if sigma[k]<=T])
                vmax[i]=vmax[i]+vmax[j]+1
                T-=sigma[j]
    #Compute the bound coming from Cauchy-Schwartz inequality
    for i in range(1,len(sigma)):
        CS_bound= int(math.sqrt(p - sigma[i]*sigma[i]))
        vmax[i]=min(CS_bound, vmax[i])
    
    return vmax

def CM_generator(sigma, vmax):
    ##Iterates through all vectors in a changemaker lattice
    ##whose coordinates satisfy |v[i]|\leq vmax[i] for all i.
    n=len(sigma)
    
    v=[-vmax[i] for i in range(0,n)]
    k=0
    while True:
        #Check whether there is a choice final coordinate to
        #put vector in CM lattice. If so, yield that vector.
        t= sum([sigma[i]*v[i] for i in range(0,n-1)])
        if t%sigma[-1]==0:
            v[-1]=-t//sigma[-1]
            if v[-1]>=-vmax[-1] and v[-1]<=vmax[-1]:
                yield v
        #Now increment v.
        while k<n-1 and v[k]+1>vmax[k]:
            v[k]=-vmax[k]
            k=k+1
        if k<n-1:
            v[k]+=1
            k=0
        else:
            break
    
def list_vertices(sigma, quick=False):
    ##generate a list of candidate vertices with norm at least 3.
    ##If the quick flag is set to true, this does not
    ##generate precisely the set of all irreducibles.
    ##p=norm(sigma)
    n=len(sigma)
    irred_list=[]
    
    #Vector defining the bounds on the search space
    vmax=vertex_bounds(sigma)

    #Modify vmax if we are doing a quick search
    if quick:
        vmax=[min(2, vmax[i]) for i in range(0,n)]
        for i in range(0,n):
            if sigma[i]==sigma[-1]:
                vmax[i]=1
    
    
    for v in CM_generator(sigma,vmax):
        v_irred_flag=True
        
        ##Compare v against all other potential irreducibles.
        if v_irred_flag:
            for vtest in irred_list:
                if irred_check(v,vtest)==False:
                    v_irred_flag=False
                    break
        #if v is potentially irreducible, we use it filter out any
        #non-irreducibles in irred_list and add it to irred_list.
        if v_irred_flag:
            irred_list=[w for w in irred_list if irred_check(w,v)]
            irred_list+=[list(v)]
    return irred_list

def half_int_OSB_search(sigma, quick=False):
    ##Given a changemaker vector search for an OSB for the corresponding
    ##n+1/2 changemaker lattice
    p=2*norm(sigma)+1
    n=len(sigma)
    new_sigma=[0,1]+sigma

    ##populate potential obtuse superbases with known elements
    initial_vertices=[[1,1,-1]+[0]*(n-1)]
    k=1
    while sigma[k]==1:
        initial_vertices+=[[0]*(k+1)+[1,-1]+[0]*(n-k-1)]
        k+=1
    vertex_pool=[]
    
    for z in list_vertices(sigma,quick):
        z_new=[0,0]+z
        ##check z compatible with initial vertices
        z_flag=True
        for w in initial_vertices:
            if sum([w[i]*z_new[i] for i in range(0,len(w))])>0:
                z_flag=False
        if z_flag:
            vertex_pool+=[z_new]        

    #Now consider all possible combinations of vertices.
    for t in obtuse_subsets(vertex_pool,n-len(initial_vertices)):
        #print(t)
        vertex_list=initial_vertices+list(t)
        if obtuse_test(vertex_list,p):
            return sp.Matrix(vertex_list)
    return False
    
def int_OSB_search(sigma, quick=False):
    ##Search for an obtuse superbase. Function returns an OSB
    #if it finds one. Returns false otherwise. The optional flag quick
    ##can be used to accelerate the search. When true the flag restricts
    ##the search of irreducibles to vectors with coefficients at most 2.
    ##Conjecturally, this is should still always find an OSB if it exists.
    ##However, we can only rigourously rule out the existence of
    ##an OSB if we run the algorithm with the quick flag set to False.
    ##This implementation is improved
    ## adding norm 2 vertices to the basis at the start

    p=norm(sigma)
    n=len(sigma)
    
    #Create a list of norm 2 vectors that we will put in our basis.
    norm2_vertices=[]
    for i in range(1,n):
        if sigma[i]==sigma[i-1]:
            z=[0]*n
            z[i]=1
            z[i-1]=-1
            norm2_vertices+=[list(z)]

    #Filter our set of irreducibles by picking those with norm >2 and
    #pairing 0 or -1 with the norm two vectors
    vertex_pool=[]
    for z in list_vertices(sigma,quick):
        t=[sum([w[i]*z[i] for i in range(0,n)]) for w in norm2_vertices]
        if len(t)==0 or (min(t)>=-1 and max(t)<=0):
            vertex_pool+=[z]

    #Now consider all possible combinations of vertices.
    for t in obtuse_subsets(vertex_pool,n-len(norm2_vertices)-1):
        vertex_list=norm2_vertices+list(t)
        if obtuse_test(vertex_list,p):
            return sp.Matrix(vertex_list)
        
    return []

def obtuse_test(v_list, p):
    ##Check whether a given list of vectors forms an OSB for a lattice of discriminant p
    n=len(v_list[0])
    last_vertex=[sum(-v[k] for v in v_list) for k in range(n)]
    if max(sum([v[i]*last_vertex[i] for i in range(n)]) for v in v_list)>0:
        return False
    M=sp.Matrix(v_list)
    Q=M*(M.T)
    for i in range(0,len(v_list)):
        for j in range(i+1,len(v_list)):
            if Q[i,j]>0:
                return False            
    return Q.det()==p    
    
def vertex_filter(v,w):
    ##function to decide if two vectors can appear
    ##in the same OSB.
    return sum(v[i]*w[i] for i in range(len(v)))<=0
    t=sum(v[i]*w[i] for i in range(len(v)))
    return (t<=0 and t>-max(norm(v),norm(w)))

def obtuse_subsets(vertices, r):
    ##Given a list of vectors return subsets of size of r such all pairs
    ##satisfy v.w<=0. This is done via a breadth first search.
    v=vertices
    clist=[]
    n=len(vertices)

    for i in range(n):
        clist+=[[j for j in range(i+1,n) if vertex_filter(v[i],v[j])]]

    sols=[[i] for i in range(n)]
    for k in range(r-1):
        new_sols=[]
        for sol in sols:                        
            new_sols+= [sol + [j] for j in clist[sol[-1]]]
        sols=list(new_sols)
        #print(len(sols), sols)
    
    for sol in sols:
        yield [v[i] for i in sol]

def adhoc_tests(stable_coefs):
    ##Some tests for whether a given set of cable coefficients
    ##can possibly support an OSB. Returns false if there cannot
    ##exist an OSB. Returns true if inconclusive. These methods
    ##are not necessary they are simply used to accelerate running
    ##times.
    stable=sorted(stable_coefs)
    ##If the stable coefficents contain 4,4,4,4,3,3,2 then
    ##there is no OSB.
    if stable.count(4)>=4 and stable.count(3)>=2 and stable.count(2)>=1:
        return False

    ##If the stable coefficents contain 3,3,3,3,2,2,2 then
    ##there is no OSB.
    if stable.count(3)>=4 and stable.count(2)>=3:
        return False
    ##The obstruction based on Corollary ?? from the paper.
    for k in range(0,len(stable)-1):
        N=stable.count(stable[k])
        if N>=4 and (N-1)*stable[k]>stable[k+1]>stable[k]:
            return False

    return True

def verify_stable_in_D(stable_coefs, quick=False):
    ##Verify whether a given set of stable coefficients can come from
    ##the Alexander polynomial of a knot in D by searching the N-1/2
    ##changemaker lattice for an OSB.
    stable=sorted(stable_coefs)
    n=len(stable)
    ##Determine number of coefficients equal to one to get N-1 CM-vector
    t= max([stable[k]-sum([stable[j] for j in range(0,k)]) for k in range(0,n)])
    sigma=[1]*(t-1)+stable
    
    if half_int_OSB_search(sigma,quick)==False:
        return False
    else:
        return True
        
    

def find_OSB_slopes(stable_coefs):
    ##Input the stable coefficients. Returns a rigourously verified
    ##list of integer coefficients for which there is an OSB. Returns a
    ##list of slopes and an OSB in matrix form.
    output=[]
    if adhoc_tests(stable_coefs)==False:
        return output
    
    stable=sorted(stable_coefs)

    ##Check whether these stable coefficients support a decomposable lattice.
    decomposable= stable_is_decomposable(stable)

    slopes=[]
    ##Work out which slopes can conceivably admit an OSB.
    if decomposable:
        slopes=[0,1,2]
    elif is_CM([1]*(stable[0]-1)+stable):
        slopes=[0,1]
    else:
        slopes=[1,2]
    
    #First perform a quick search to find OSBs with small coefficients.
    for k in slopes:
        sigma=[1]*k+[1]*(stable[0]-1)+stable
        n=norm(sigma)
        
        if is_CM(sigma):
            ##First run a quick search
            result=int_OSB_search(sigma,quick=True)
            if len(result)>0:
                output+=[[n,result]]
            else:
                ##If an OSB not found quickly, run a full search instead.
                result=int_OSB_search(sigma, quick=False)
                if len(result)>0:
                    output+=[[n,result]]
            
    return output

# t_list=[[2],[3],[4], [2,2],[2,2,2],[3,2,2],[3,2,2,2]]

# p_list=[[12, 9, 5, 4, 2],
# [16, 12, 7, 4, 2],
# [18, 13, 7, 6, 2, 2],
# [17, 14, 5, 5, 4, 2],
# [26, 17, 12, 5, 4, 2]
# ]

# c_list=[[12, 9, 5, 4, 2],
# [16, 12, 7, 4, 2],
# [17, 14, 5, 5, 4, 2],
# [17, 13, 7, 6, 3],
# [18, 13, 7, 6, 2, 2],
# [26, 17, 12, 5, 4, 2],
# [23, 19, 7, 7, 4, 2],
# [23, 17, 10, 6, 3],
# [17, 17, 13, 7, 6, 3],
# [28, 12, 12, 7, 4, 2],
# [24, 18, 11, 6, 2, 2],
# [12, 12, 9, 5, 4, 2],
# [17, 17, 14, 5, 5, 4, 2],
# [18, 18, 13, 7, 6, 2, 2]
# ]
# import time
# start_time = time.time()

# for c in t_list:
#     start_time=time.time()
#     print(c)
#     print(verify_stable_in_D(c,True))
#     print("Example time: %f s" %(time.time()-start_time))
In [3]:
##Stable Coefficients:
##BL_knot:[1, 1, 1, 1, 0](0,0) [12, 9, 5, 4, 2]
##BL_knot:[1, 1, 0, 1, 1](0,0) [16, 12, 7, 4, 2]
##BL_knot:[1, 1, 1, 2, 0](0,0) [12, 12, 9, 5, 4, 2]
##BL_knot:[1, 1, 2, 1, 0](0,0) [17, 14, 5, 5, 4, 2]
##BL_knot:[1, 2, 1, 1, 0](0,0) [17, 13, 7, 6, 3]
##BL_knot:[2, 1, 1, 1, 0](0,0) [18, 13, 7, 6, 2, 2]
##BL_knot:[1, 1, 1, 1, 1](0,0) [26, 17, 12, 5, 4, 2]
##BL_knot:[1, 1, 0, 2, 1](0,0) [23, 19, 7, 7, 4, 2]
##BL_knot:[1, 2, 0, 1, 1](0,0) [23, 17, 10, 6, 3]
##BL_knot:[1, 1, 2, 2, 0](0,0) [17, 17, 14, 5, 5, 4, 2]
##BL_knot:[1, 2, 1, 2, 0](0,0) [17, 17, 13, 7, 6, 3]
##BL_knot:[2, 1, 1, 2, 0](0,0) [18, 18, 13, 7, 6, 2, 2]
##BL_knot:[1, 1, 0, 1, 2](0,0) [28, 12, 12, 7, 4, 2]
##BL_knot:[2, 1, 0, 1, 1](0,0) [24, 18, 11, 6, 2, 2]

BL_list=[[12, 9, 5, 4, 2],
[16, 12, 7, 4, 2],
[12, 12, 9, 5, 4, 2],
[17, 14, 5, 5, 4, 2],
[17, 13, 7, 6, 3],
[18, 13, 7, 6, 2, 2],
[26, 17, 12, 5, 4, 2],
[23, 19, 7, 7, 4, 2],
[23, 17, 10, 6, 3],
[17, 17, 14, 5, 5, 4, 2],
[17, 17, 13, 7, 6, 3],
[18, 18, 13, 7, 6, 2, 2],
[28, 12, 12, 7, 4, 2],
[24, 18, 11, 6, 2, 2]]
In [4]:
for stable in BL_list:
    start_time=time.time()
    print(stable)
    print(verify_stable_in_D(stable,True))
    print("Example time: %f s" %(time.time()-start_time))
[12, 9, 5, 4, 2]
False
Example time: 0.329038 s
[16, 12, 7, 4, 2]
False
Example time: 0.559223 s
[12, 12, 9, 5, 4, 2]
False
Example time: 5.472702 s
[17, 14, 5, 5, 4, 2]
False
Example time: 4.803319 s
[17, 13, 7, 6, 3]
False
Example time: 0.282121 s
[18, 13, 7, 6, 2, 2]
False
Example time: 5.118518 s
[26, 17, 12, 5, 4, 2]
False
Example time: 11.103709 s
[23, 19, 7, 7, 4, 2]
False
Example time: 13.502366 s
[23, 17, 10, 6, 3]
False
Example time: 0.531706 s
[17, 17, 14, 5, 5, 4, 2]
False
Example time: 166.902848 s
[17, 17, 13, 7, 6, 3]
False
Example time: 4.599586 s
[18, 18, 13, 7, 6, 2, 2]
False
Example time: 143.677569 s
[28, 12, 12, 7, 4, 2]
False
Example time: 11.058084 s
[24, 18, 11, 6, 2, 2]
False
Example time: 16.205099 s